package DynamicProgram.completeBag;

/**
 * @ClassName CompleteBagProblem
 * @Description TODO
 * @Author lenovo
 * @Date 2023-08-09 10:23
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class CompleteBagProblem {


    //先遍历物品，再遍历背包
    //有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
    //完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
    private static void testCompletePack() {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        //dp[i] zhzhon
        int[] dp = new int[bagWeight + 1];

        //0-1背包问题
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        //完全背包
//        for (int i = 0; i < weight.length; i++) {
//            for (int j = weight[i]; j <= bagWeight; j++) {
//                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
//            }
//        }

        for (int maxValue : dp) {
            System.out.println(maxValue + "   ");
        }
    }

    public static void main(String[] args) {
        testCompletePack();
//        Double a = 100.01%;
//        Double b = 12.0%;
//        System.out.println(String.format("%.2f",b));

    }
}